#!/usr/bin/env python
#encoding: latin1

import quicksort

class Trabajo(object):

	def __init__(self, numero, tiempo, beneficio, vencimiento):
		self._numero = int(numero)
		self._tiempo = int(tiempo)
		self._beneficio = int(beneficio)
		self._vencimiento = int(vencimiento)

	@property
	def numero(self):
		return self._numero

	@property
	def tiempo(self):
		return self._tiempo

	@property
	def beneficio(self):
		return self._beneficio

	@property
	def vencimiento(self):
		return self._vencimiento


def iniciar_programa():
	print "TP3 de Teoría de Algoritmos. Planificación de órdenes de trabajo."
	while True:
		try:
			archivo = raw_input("Nombre del archivo a procesar: ")
			break
		except IOError:
			print "El archivo es inválido."
	return archivo


def leer_archivo(nombre_archivo):
	"""Pre: cada línea del archivo debe tener el formato: duración, beneficio, vencimiento.
	Post: devuelve los trabajos en una lista."""
	try:
		archivo = open(nombre_archivo)
		trabajos = []
		numero = 0
		for linea in archivo:
			numero += 1
			tiempo, beneficio, vencimiento = linea.rstrip('\n').split(",")
			trabajo = Trabajo(numero, tiempo, beneficio, vencimiento)
			trabajos.append(trabajo)
		archivo.close()

	except (IOError, ValueError):
		print "El archivo es inválido"
		trabajos = None	

	return trabajos

def comparar_trabajos(trabajo1, trabajo2):
	""" Funcion de comparacion de trabajos segun el vencimiento."""
	if trabajo1.vencimiento < trabajo2.vencimiento:
		return -1
	elif trabajo1.vencimiento > trabajo2.vencimiento:
		return 1
	else:
		return 0


def calcular_puntoA(trabajos):
	"""Recibe una lista con Trabajos. Calcula la solución óptima e imprime el valor del beneficio óptimo."""
	quicksort.quick_sort(trabajos, comparar_trabajos)

	matriz = armar_matriz(trabajos)

	opt(len(matriz)-1,len(matriz[0])-1,matriz,trabajos)
	
	print "Beneficio óptimo: " + str(matriz[len(matriz)-1][len(matriz[0])-1])


def armar_matriz(trabajos):
	"""Arma la matriz de valores."""
	matriz=[[]]
	vencimiento_maximo = 0
	for trabajo in trabajos:
		matriz.append([])
		if trabajo.vencimiento > vencimiento_maximo:
			vencimiento_maximo = trabajo.vencimiento
	for x in range(vencimiento_maximo+1):
		matriz[0].append(0)

	n = 1
	for trabajo in trabajos:
		for tiempo in range(vencimiento_maximo+1):
			t1 = min(tiempo, trabajo.vencimiento) - trabajo.tiempo
			if 0 > t1:
				matriz[n].append(matriz[n-1][tiempo])
			else:
				resultado = max(matriz[n-1][tiempo], trabajo.beneficio + matriz[n-1][t1])
				matriz[n].append(resultado)
		n+=1
	return matriz		
	
def opt(i,t, matriz, trabajos):
	"""Recibe i y t, índices de la matriz, de trabajo y tiempo respectivamente. Recibe también la matriz con los valores, y los trabajos.
	Pre: i y t son índices positivos.
	Post: imprime el trabajo que se toma como parte de la solución óptima junto al tiempo en el cual es ejecutado. """
	if i == 0:
		return
	if matriz[i][t] == matriz[i-1][t]:
		opt(i-1,t,matriz,trabajos)
	else:
		t1= min(t, trabajos[i-1].vencimiento) - trabajos[i-1].tiempo
		opt(i-1,t1,matriz,trabajos)
		print "Trabajo " + str(trabajos[i-1].numero) +"("+ str(trabajos[i-1].tiempo), str(trabajos[i-1].beneficio), str(trabajos[i-1].vencimiento) +")" + " en tiempo " + str(t1) 

def main():
	nombre_archivo = iniciar_programa()
	trabajos = leer_archivo(nombre_archivo)

	if trabajos is not None:
		calcular_puntoA(trabajos)

main()

